Automne's Shadow.

Plaid CTF 2019 Project Eulernt WriteUp

gmpy2
2019/04/27 Share

Crypto

谢谢大佬分享：https://github.com/hyperreality/ctf-writeups/tree/master/2019-plaidctf

这道Misc题我将它归类为Crypto，因为我觉得其中的运算更贴近数学领域。

首先看一下题目贴出的脚本：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#!/usr/bin/env python3
import gmpy2

from decimal import Decimal

N = int(gmpy2.fac(333))
#N = 10334465434588059156093965538297516550622260041682062823432902469783188597914276568552700194849877929894375950252570477080418352732597658745665925604704669227133726477243854317836635130694123893711638533001980496229875665476598568821806170303765540489814402234159901540440432134155844542962445153646330595588291605924429211352279943471372817279938720974895260387784578239150931816946786416232516666251965421919651838044618050991294403546958930745419743836966520198735201123255884089263272829846640538826979843642885775791641575109178753509580001660392092396798648924375401024147883702298145910046889402880394195369984000000000000000000000000000000000000000000000000000000000000000000000000000000000
sN = int(gmpy2.isqrt(N))
#sN = 3214726338988757399964463840205273148284735043324463579894976679845078166928105412104944973948893914339037572694382785661727648297539107767478128297633669341356440278480314502443731079340424764653103468238563073341496690901434197268615240607985890327844073738551115260849983966971570699838147501655616953786428037017304945538845583678438817092853062

k = int(input("Enter number: "))

goodness = Decimal(abs(k - sN)) / sN 

if k and N % k == 0 and goodness < 1e-8:
    print(open('/home/eulernt/flag.txt').read())
elif k and N % k == 0 and goodness < 1e-4:
	print("Good work! You're getting there.")
else:
    print("Nope!")

需要注意gmpy2.fac(333)是333的阶乘，123…*333，表示为333！数学都忘光了哈哈

gmpy2.isqrt(N)是对N开根号，然后程序的逻辑就是要我们求一个同时满足N % k == 0并且Decimal(abs(k - sN)) / sN < 1e-8的整数

开始的时候尝试使用z3进行约束求解，但是不可行。

其实知道是阶乘运算之后，就可以挨个因子去测试，最终在相邻的因子间再做处理，直到得到小于1e-8的数字。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#!/usr/bin/env python3

import gmpy2
from decimal import Decimal

N = int(gmpy2.fac(333))
sN = int(gmpy2.isqrt(N))

lastgoodness = 2**32

for i in range(333):
    k = int(gmpy2.fac(i))
    goodness = Decimal(abs(k - sN)) / sN
    print(goodness)
    if goodness > lastgoodness:
        i = i - 1    #i=189进入条件
        break
    lastgoodness = goodness

k = int(gmpy2.fac(i))
factor = i - 1
direction = 0

while not (N % k == 0 and goodness < 1e-8):
    x = int(gmpy2.fac(factor))

    if direction == 0:
        k = k + x
    else:
        k = k - x

    goodness = Decimal(abs(k - sN)) / sN

    print("%s %s %s" % (factor, N % k == 0, goodness))
    if goodness > lastgoodness:
        if factor != 1:
            factor = factor - 1
        direction = direction ^ 1
    lastgoodness = goodness

print("Solution is %s" % k)

最终得到满足条件的整数：

...
...
0.9995539612695387806518950648
187
0.9161447186732907625562721817
188
14.84864817074804587686455766
189
187 True 0.9156986799428295432081672465
187 True 0.9152526412123683238600623113
187 True 0.9148066024819071045119573761
...
...
184 True 3.447727270606120732779613170E-9
Solution is 3214726350072257066431779235750840929219380986500824976682691501005045658412547178850613283446572126454848437809927102959300721991188613732891480424816898090401474090228882047516881401960775657269052068936565791968436947912579621385034525890482950410176853479808655903537176316978841327570169928228012032000000000000000000000000000000000000000000000

原文作者: Automne

原文链接: https://ce-automne.github.io/2019/04/27/Plaid-CTF-2019-Project Eulernt-WriteUp/

发表日期: April 27th 2019, 1:16:00 pm

版权声明: 本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
Total : 62
2021
2020
2019
2018
2017
lfsr z3 python reverse fat git broadcastreceiver sha-1 cbc sqli sqlite golang race condition luks hashcat photorec MAC sso oauth 2.0 padding oracle csp xss abe vdex ransomware frida ndk pwntools hashpumpy sourceleakhacker ecb socat fastjson JdbcRowsetImpl idea servlet volatility inet_aton boneh durfee lcg rabin egcd cipolla's algorithm spi snakeyaml ScriptEngineManager malware codereflect mysql yara plugin deserialization log4j rsa binary javascript prototype pollution nodejs shiro ysoserial primefac rsatool ssl AES tshark gmpy2 RsaCtfTool Hex flask ssti ecc Modular operation WebGoat8 order by tomcat nim game .iso gpg outguess sage google cloud sdk zsteg base58 fermat multi-primes prng rmi jndi Paillier Cryptosystem rsa lsb oracle SQL Injection ping delay xor CAS 单点登录 渗透测试 weblogic xxe reflect 010 editor gcd
Crypto Android Web Forensics Misc